package leetcode.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leetcode-hot100 : 合并区间
 * 测试链接 : https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
 *
 *
 * 以数组 intervals 表示若干个区间的集合，
 * 其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，
 * 并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
 *
 *
 */
public class MergeIntervals {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        //按左端点从小到大排序,按左端点排序可以保证合并的是连续的区间
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> merge = new ArrayList();
        for(int i = 0; i < n; i++){
            int start = intervals[i][0];
            int end = intervals[i][1];
            //第一个区间加入合并后的列表
            //如果合并后列表的右边界小于当前区间的左边界，证明没有产生重合，直接加入列表
            if(merge.size() == 0 || merge.get(merge.size() - 1)[1] < start){
                merge.add(new int[]{start, end});
            }else{
                //更改右边界，因为数组以及按左边界排好序了，左边界当前一定是最小
                //所以只需要不断扩展右边界
                merge.get(merge.size() - 1)[1] = Math.max(merge.get(merge.size() - 1)[1], end);
            }
        }
        return merge.toArray(new int[merge.size()][]);
    }
}
